// 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

// 说明：解集不能包含重复的子集。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const subsets = function (nums: number[]) {
    const res: number[][] = []; // 结果数组
    const path: number[] = []; // 当前路径数组
    subsets_DFS(nums, res, path, 0);
    return res;
};

function subsets_DFS(nums: number[], res: number[][],
    path: number[], begin: number) {
    // 将当前组合加入结果数组
    res.push(Array.from(path));
    if (begin === nums.length) { // 递归出口
        return;
    }
    for (let i = begin; i < nums.length; i++) {
        path.push(nums[i]);
        // 这里注意！begin应该是 i + 1因为不能往后选
        subsets_DFS(nums, res, path, i + 1);
        // 回溯部分
        path.pop();
    }
}


subsets([1, 2, 3]);

// 这道题目也是一道比较经典的深度优先遍历结合回溯算法的题目
// 我们依然是使用深度优先遍历来模拟选择的过程
// 之后使用回溯算法来进行状态的重置，以方便进行重新选择
// 因为是求子集，所以每一轮循环都算；即只要进入了当前的递归中就把路径数组加入结果中
// 但这里因为题目要求不能出现结果重复，例如[2,3]和[3,2]
// 我们思考其实理解过来就是要求在选择的过程中，我们需要以当前的基点开始往右搜索
// 而不能进行回头的搜索，这里其实就要引入一个begin变量
// 但需要额外注意的是，每一轮递归的begin我们其实应该设置成当前的索引i+1
// 这里会很容易犯错
// 思考完之后，递归出口也很容易求得，就是当起点begin变量超出数组索引时，递归结束

